package Simple2;



/**
 * Find the number appears in the array whose appearance times larger than
 * half size of the array.
 * If the array doesn't have such a number, return null;
 * 
 * like [1,1,2,2,2] then return 2;
 * @author YC
 *
 */
public class Halftimes_of_array {
	
	public static String solution(int[] array){
		if(array.length==0) return null;
		if(array.length==1) return String.valueOf(array[0]);
		
		int count=0,temp=array[0];
		for(int i=0;i<array.length;++i){
			if(count==0){
				temp = array[i];
			}
			if(array[i]==temp)
				count++;
			else 
				count--;
					
		}
		
		//This code cannot handle the case that {1,1,2,2,1} (count==1, and should return 1)
		//If we change code to "(count>0)",cannot handle {1,2,3}	
		
//		if(count>1)
//			return String.valueOf(temp);
//		else 
//			return null;
		
		
		count=0;
		for(int i=0;i<array.length;++i){
			if(array[i]==temp)
				count++;
		}
		if(count>array.length/2)
			return String.valueOf(temp);
		else
			return null;
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] test = {1,1,2,2,1};
		System.out.print(solution(test));
	}

}
